
#ifndef __CRTOS_HEAP_h
#define __CRTOS_HEAP_h

#ifdef __cplusplus
extern "C" {
#endif

/*
 *  Status codes for heap_extend
 */
typedef unsigned long unsigned32;
typedef int boolean;
#define TRUE 1;
#define FALSE 0;


/*
 *  Constants used in the size/used field of each heap block to
 *  indicate when a block is free or in use.
 */

#define CPU_ALIGNMENT      4
#define CPU_HEAP_ALIGNMENT CPU_ALIGNMENT

#define HEAP_BLOCK_USED    1           /* indicates block is in use */
#define HEAP_BLOCK_FREE    0           /* indicates block is free */

/*
 *  The size/used field value for the dummy front and back flags.
 */

#define HEAP_DUMMY_FLAG    (0 + HEAP_BLOCK_USED)

/*
 *  The following constants reflect various requirements of the
 *  heap data structures which impact the management of a heap.
 *
 * NOTE:   Because free block overhead is greater than used block
 *         overhead AND a portion of the allocated space is from
 *         the extra free block overhead, the absolute lower bound
 *         of the minimum fragment size is equal to the size of
 *         the free block overhead.
 */

#define HEAP_OVERHEAD   (sizeof( unsigned32 ) * 2)
/* size dummy first and last blocks */

#define HEAP_BLOCK_USED_OVERHEAD   (sizeof( void * ) * 2)
/* num bytes overhead in used block */

#define HEAP_MINIMUM_SIZE   (HEAP_OVERHEAD + sizeof (Heap_Block))
/* min number of bytes the user may */
/*   specify for the heap size      */

/*
 *  The following defines the data structure used to manage
 *  individual blocks in a heap.   When the block is allocated, the
 *  next and previous fields are not used by the Heap Handler
 *  and thus the address returned for the block starts at
 *  the address of the next field.
 *
 *  NOTE:  The next and previous pointers are only valid when the
 *         block is free.  Caution must be exercised to insure that
 *         allocated blocks are large enough to contain them and
 *         that they are not accidentally overwritten when the
 *         block is actually allocated.
 */

typedef struct Heap_Block_struct Heap_Block;

struct Heap_Block_struct {
  unsigned32  back_flag;   /* size and status of prev block */
  unsigned32  front_flag;  /* size and status of block */
  Heap_Block *next;        /* pointer to next block */
  Heap_Block *previous;    /* pointer to previous block */
};

/*
 *  The following defines the control block used to manage each heap.
 *
 *  NOTE:
 *
 *  This structure is layed out such that it can be used a a dummy
 *  first and last block on the free block chain.  The extra padding
 *  insures the dummy last block is the correct size.
 *
 *  The first Heap_Block starts at first while the second starts at
 *  final.  This is effectively the same trick as is used in the Chain
 *  Handler.
 */

typedef struct {
  Heap_Block *start;       /* first valid block address in heap */
  Heap_Block *final;       /* last valid block address in heap */

  Heap_Block *first;       /* pointer to first block in heap */
  Heap_Block *permanent_null;  /* always NULL pointer */
  Heap_Block *last;        /* pointer to last block in heap */
  unsigned32  page_size;   /* allocation unit */
  unsigned32  reserved;
}   Heap_Control;

/*
 *  _Heap_Initialize
 *
 *  DESCRIPTION:
 *
 *  This routine initializes the_heap record to manage the
 *  contiguous heap of size bytes which starts at starting_address.
 *  Blocks of memory are allocated from the heap in multiples of
 *  page_size byte units.
 */

unsigned32 _Crtl_Heap_Initialize(
  Heap_Control *the_heap,
  void         *starting_address,
  unsigned32    size,
  unsigned32    page_size
);


/*
 *  _Heap_Allocate
 *
 *  DESCRIPTION:
 *
 *  DESCRIPTION:
 *
 *  This function attempts to allocate a block of size bytes from
 *  the_heap.  If insufficient memory is free in the_heap to allocate
 *  a  block of the requested size, then NULL is returned.
 */

void *_Crtl_Heap_Allocate(
  Heap_Control *the_heap,
  unsigned32    size
);



/*
 *  _Heap_Free
 *
 *  DESCRIPTION:
 *
 *  This routine returns the block of memory which begins
 *  at starting_address to the_heap.  Any coalescing which is
 *  possible with the freeing of this routine is performed.
 */

boolean _Crtl_Heap_Free(
  Heap_Control *the_heap,
  void         *start_address
);


/*PAGE
 *
 *  _Addresses_Add_offset
 *
 *  DESCRIPTION:
 *
 *  This function is used to add an offset to a base address.
 *  It returns the resulting address.  This address is typically
 *  converted to an access type before being used further.
 */

inline void *_Addresses_Add_offset (
  void       *base,
  unsigned32  offset
)
{
  return (void *)((char *)base + offset);
}

/*PAGE
 *
 *  _Addresses_Subtract_offset
 *
 *  DESCRIPTION:
 *
 *  This function is used to subtract an offset from a base
 *  address.  It returns the resulting address.  This address is
 *  typically converted to an access type before being used further.
 */

inline void *_Addresses_Subtract_offset (
  void       *base,
  unsigned32  offset
)
{
  return (void *)((char *)base - offset);
}

/*PAGE
 *
 *  _Addresses_Subtract
 *
 *  DESCRIPTION:
 *
 *  This function is used to subtract two addresses.  It returns the
 *  resulting offset.
 *
 *  NOTE:  The cast of an address to an unsigned32 makes this code
 *         dependent on an addresses being thirty two bits.
 */

inline unsigned32 _Addresses_Subtract (
  void *left,
  void *right
)
{
  return ((char *) left - (char *) right);
}

/*PAGE
 *
 *  _Addresses_Is_aligned
 *
 *  DESCRIPTION:
 *
 *  This function returns TRUE if the given address is correctly
 *  aligned for this processor and FALSE otherwise.  Proper alignment
 *  is based on correctness and efficiency.
 */

inline boolean _Addresses_Is_aligned (
  void *address
)
{
    return ( ( (unsigned32)address % CPU_ALIGNMENT ) == 0 );
}

/*PAGE
 *
 *  _Addresses_Is_in_range
 *
 *  DESCRIPTION:
 *
 *  This function returns TRUE if the given address is within the
 *  memory range specified and FALSE otherwise.  base is the address
 *  of the first byte in the memory range and limit is the address
 *  of the last byte in the memory range.  The base address is
 *  assumed to be lower than the limit address.
 */

inline boolean _Addresses_Is_in_range (
  void *address,
  void *base,
  void *limit
)
{
  return ( address >= base && address <= limit );
}


/*PAGE
 *
 *  _Heap_Head
 *
 *  DESCRIPTION:
 *
 *  This function returns the head of the specified heap.
 */

inline Heap_Block *_Heap_Head (
  Heap_Control *the_heap
)
{
  return (Heap_Block *)&the_heap->start;
}

/*PAGE
 *
 *  _Heap_Tail
 *
 *  DESCRIPTION:
 *
 *  This function returns the tail of the specified heap.
 */

inline Heap_Block *_Heap_Tail (
  Heap_Control *the_heap
)
{
  return (Heap_Block *)&the_heap->final;
}

/*PAGE
 *
 *  _Heap_Previous_block
 *
 *  DESCRIPTION:
 *
 *  This function returns the address of the block which physically
 *  precedes the_block in memory.
 */

inline Heap_Block *_Heap_Previous_block (
  Heap_Block *the_block
)
{
  return (Heap_Block *) _Addresses_Subtract_offset(
                          (void *)the_block,
                          the_block->back_flag & ~ HEAP_BLOCK_USED
                        );
}

/*PAGE
 *
 *  _Heap_Next_block
 *
 *  DESCRIPTION:
 *
 *  This function returns the address of the block which physically
 *  follows the_block in memory.
 *
 *  NOTE: Next_block assumes that the block is free.
 */

inline Heap_Block *_Heap_Next_block (
  Heap_Block *the_block
)
{
  return (Heap_Block *) _Addresses_Add_offset(
                          (void *)the_block,
                          the_block->front_flag & ~ HEAP_BLOCK_USED
                        );
}

/*PAGE
 *
 *  _Heap_Block_at
 *
 *  DESCRIPTION:
 *
 *  This function calculates and returns a block's location (address)
 *  in the heap based upon a base address and an offset.
 */

inline Heap_Block *_Heap_Block_at(
  void       *base,
  unsigned32  offset
)
{
  return (Heap_Block *) _Addresses_Add_offset( (void *)base, offset );
}

/*PAGE
 *
 *  _Heap_User_block_at
 *
 *  DESCRIPTION:
 *
 *  XXX
 */

inline Heap_Block *_Heap_User_block_at(
  void       *base
)
{
  unsigned32         offset;

  offset = *(((unsigned32 *) base) - 1);
  return _Heap_Block_at( base, -offset + -HEAP_BLOCK_USED_OVERHEAD);
}

/*PAGE
 *
 *  _Heap_Is_previous_block_free
 *
 *  DESCRIPTION:
 *
 *  This function returns TRUE if the previous block of the_block
 *  is free, and FALSE otherwise.
 */

inline boolean _Heap_Is_previous_block_free (
  Heap_Block *the_block
)
{
  return !(the_block->back_flag & HEAP_BLOCK_USED);
}

/*PAGE
 *
 *  _Heap_Is_block_free
 *
 *  DESCRIPTION:
 *
 *  This function returns TRUE if the block is free, and FALSE otherwise.
 */

inline boolean _Heap_Is_block_free (
  Heap_Block *the_block
)
{
  return !(the_block->front_flag & HEAP_BLOCK_USED);
}

/*PAGE
 *
 *  _Heap_Is_block_used
 *
 *  DESCRIPTION:
 *
 *  This function returns TRUE if the block is currently allocated,
 *  and FALSE otherwise.
 */

inline boolean _Heap_Is_block_used (
  Heap_Block *the_block
)
{
  return (the_block->front_flag & HEAP_BLOCK_USED);
}

/*PAGE
 *
 *  _Heap_Block_size
 *
 *  DESCRIPTION:
 *
 *  This function returns the size of the_block in bytes.
 */

inline unsigned32 _Heap_Block_size (
  Heap_Block *the_block
)
{
  return (the_block->front_flag & ~HEAP_BLOCK_USED);
}

/*PAGE
 *
 *  _Heap_Start_of_user_area
 *
 *  DESCRIPTION:
 *
 *  This function returns the starting address of the portion of the block
 *  which the user may access.
 */

inline void *_Heap_Start_of_user_area (
  Heap_Block *the_block
)
{
  return (void *) &the_block->next;
}

/*PAGE
 *
 *  _Heap_Is_block_in
 *
 *  DESCRIPTION:
 *
 *  This function returns TRUE if the_block is within the memory area
 *  managed by the_heap, and FALSE otherwise.
 */

inline boolean _Heap_Is_block_in (
  Heap_Control *the_heap,
  Heap_Block   *the_block
)
{
  return _Addresses_Is_in_range( the_block, the_heap->start, the_heap->final );
}

/*PAGE
 *
 *  _Heap_Is_page_size_valid
 *
 *  DESCRIPTION:
 *
 *  This function validates a specified heap page size.  If the page size
 *  is 0 or if lies outside a page size alignment boundary it is invalid
 *  and FALSE is returned.  Otherwise, the page size is valid and TRUE is
 *  returned.
 */

inline boolean _Heap_Is_page_size_valid(
  unsigned32 page_size
)
{
  return ((page_size != 0) &&
         ((page_size % CPU_HEAP_ALIGNMENT) == 0));
}

/*PAGE
 *
 *  _Heap_Build_flag
 *
 *  DESCRIPTION:
 *
 *  This function returns the block flag composed of size and in_use_flag.
 *  The flag returned is suitable for use as a back or front flag in a
 *  heap block.
 */

inline unsigned32 _Heap_Build_flag (
  unsigned32 size,
  unsigned32 in_use_flag
)
{
  return  size | in_use_flag;
}

#ifdef __cplusplus
}
#endif
#endif
/* end of include file */